/**
 * 组合总和 2
 *
 * 给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * candidates 中的每个数字在每个组合中只能使用 一次 。
 * 注意：解集不能包含重复的组合。
 *
 * 示例 1:
 * 输入: candidates = [10,1,2,7,6,1,5], target = 8,
 * 输出:
 * [
 * [1,1,6],
 * [1,2,5],
 * [1,7],
 * [2,6]
 * ]
 *
 * 示例 2:
 * 输入: candidates = [2,5,2,1,2], target = 5,
 * 输出:
 * [
 * [1,2,2],
 * [5]
 * ]
 *
 * 提示:
 * 1 <= candidates.length <= 100
 * 1 <= candidates[i] <= 50
 * 1 <= target <= 30
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1. 这题感觉和上一题差不多, 我们用深搜来写, 但是注意我们这题和上一题有点不一样,
 * 上一题中题目给的数组中的数字可以用很多次, 这题只能用一次, 这一点好解决, 我们只需要
 * 将传入 dfs 中的 下标 直接 +1就可以了, 还有一点不同, 这题中给的数组中会用重复的
 * 数字出现, 这就意味着我们加入 lists 中的 集合可能会重复, 这个也好解决, 我们只要
 * 判断下 lists 中的重复元素就可以了
 * 这题用这种方法在多个相同的数字出现时会超时
 * 所以我们还需要剪枝一次, 就是在同一层的时候我们遇到相同的数字
 * 时间复杂度: O(k * m)
 * 空间复杂度: O(n)
 *
 */
public class Main {


    // 定义为全局变量
    List<List<Integer>> lists;
    List<Integer> list;
    int[] nums;
    int tmp;
    int n;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

        // 初始化
        lists = new ArrayList<>();
        list = new ArrayList<>();
        nums = candidates;
        tmp = target;
        n = nums.length;

        // 排序
        Arrays.sort(nums);

        dfs(0, 0);

        return lists;
    }

    private void dfs(int sum, int start) {

        // 这里加上一个判断 lists 中是否有 list
//        if (sum == tmp && !lists.contains(list)) {
//            lists.add(new ArrayList<>(list));
//            return;
//        }

        if (sum == tmp) {
            lists.add(new ArrayList<>(list));
            return;
        }

        // 从 start 开始遍历
        for (int i = start; i < n; i++) {
            int current = nums[i];

            // 剪枝
            if (current + sum > tmp) {
                break;
            }

            // 剪枝, 统一层中遇到相同的元素
            // 这里我们我们的重点就是怎么确定是在同一层中
            // 我们的深搜是这一层的元素向下走, 等这层循环出来
            // 后就是上一次的同层循环了, 这时 i 就会大于 start
            // 所以我们依赖这点就可以排除同一层相同的元素
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }

            // 符合要求, 添加
            list.add(current);


            // 深搜
            dfs(sum + current, i + 1);

            // 恢复现场
            list.remove(list.size() - 1);
        }
    }
}